﻿#pragma once

/**
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给定一个整数 n，返回 n 皇后不同的解决方案的数量。

示例 :

输入: 4
输出 : 2
解释 : 4 皇后问题存在如下两个不同的解法。
[
	[".Q..",  // 解法 1
	"...Q",
	"Q...",
	"..Q."],

	["..Q.",  // 解法 2
	"Q...",
	"...Q",
	".Q.."]t
]

提示：

皇后，是国际象棋中的棋子，意味着国王的妻子。皇后只做一件事，那就是“吃子”。当她遇见可以吃的棋子时，就迅速冲上去吃掉棋子。当然，她横、竖、斜都可走一或 N - 1 步，可进可退。（引用自 百度百科 - 皇后 ）
**/

#include <iostream>


class TotalNQueens52 {

#if  1
public:
	int totalNQueens(int n)
	{
		this->result = 0;
		this->pFlagCol = new int[n];
		this->pFlagP = new int[2*n - 1];
		this->pFlagL = new int[2*n - 1];

		memset(this->pFlagCol, 0, sizeof(int) * n);
		memset(this->pFlagP, 0, sizeof(int) * (2*n - 1));
		memset(this->pFlagL, 0, sizeof(int) * (2*n - 1));

		int row = 1;		
		this->countDC = 0;

		if (n == 1)
		{
			this->result = 1;
		}
		else
		{
			int pos1of2 = n / 2 + n % 2;
			for (this->idxRow1 = 1; this->idxRow1 <= pos1of2; this->idxRow1++)
			{
				this->updateFlag(row, this->idxRow1, n, 1);

				this->processRow(row + 1, n);

				this->updateFlag(row, this->idxRow1, n, 0);
			}

			this->result += this->countDC;
		}

		return this->result;
	}

	bool processRow(int row, int n)
	{
		bool bRes = false;
		for (int col = 1; col <= n; col++)
		{

			bool posR = this->checkPos(row, col, n);
			if (!posR)
			{
				continue;
			}

			if (row == n)
			{
				bRes = true;
				this->result++;

				if (this->idxRow1 <= n / 2)
				{
					this->countDC++;
				}

				break;
			}

			this->updateFlag(row, col, n, 1);

			this->processRow(row + 1, n);

			this->updateFlag(row, col, n, 0);
		}

		return bRes;
	}

	void updateFlag(int row, int col, int n, int value)
	{
		this->pFlagCol[col - 1] = value;
		this->pFlagP[row + col - 2] = value;
		this->pFlagL[n - col + row - 1] = value;
	}

	bool checkPos(int row, int col, int n)
	{
		int idxP = row + col - 1;
		int idxL = n - col + row;

		if (this->pFlagCol[col - 1] == 0 && this->pFlagP[idxP - 1] == 0 && this->pFlagL[idxL - 1] == 0)
		{
			return true;
		}
		else
		{
			return false;
		}
	}
private:
	int result;
	int* pFlagCol;
	int* pFlagP;
	int* pFlagL;
	int idxRow1;
	int countDC;
#endif


#if 0
public:
	int totalNQueens(int n) {
		dfs(n, 0, 0, 0, 0);

		return this->res;
	}

	void dfs(int n, int row, int col, int ld, int rd) {
		if (row >= n) { res++; return; }

		// 将所有能放置 Q 的位置由 0 变成 1，以便进行后续的位遍历
		int bits = ~(col | ld | rd) & ((1 << n) - 1);
		while (bits > 0) {
			int pick = bits & -bits; // 注: x & -x
			dfs(n, row + 1, col | pick, (ld | pick) << 1, (rd | pick) >> 1);
			bits &= bits - 1; // 注: x & (x - 1)
		}
	}

private:
	int res = 0;
#endif

public:
	void test()
	{
		for (int i = 1; i <= 9; i++)
		{
			int iResult = this->totalNQueens(i);

			std::cout << i << ": " << iResult << std::endl;
		}
	}
};